Maritime search tasks are usually completed by multiple facilities. In view of the maritime cooperative search planning problem, a Memory Bank Particle Swarm Optimization (MBPSO) algorithm was proposed. Combinatorial optimization strategy and continuous optimization strategy were employed. The candidate solutions and memory bank for every single facility were constructed at first. New candidate solutions were generated based on memory consideration and random selection. Then the memory bank was updated based on a method of lattice, which means that for each lattice, there was only one candidate solution to be stored in the memory bank at most. Based on that, the diversity of the solutions in the memory bank could be ensured and effective global search was performed. At last, initial cooperative search plans were generated by combing candidate solutions in the memory bank randomly. Based on the strategy of Particle Swarm Optimization (PSO), effective local search was performed by searching around the solutions with high quality. Experimental results show that, in terms of efficiency, the time consumed by the proposed algorithm is short; the lowest variance is acquired and the success probability can be increased by 1% to 5%. The proposed algorithm can be applied to make maritime cooperative search plans effectively.